/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class ReachingPoints {
	public boolean reachingPoints(int sx, int sy, int tx, int ty) {
		Queue<int[]> queue = new LinkedList<>();
		int[] start = new int[] { sx, sy };
		queue.add(start);
		Set<String> visited = new HashSet<>();
		visited.add(start[0] + "," + start[1]);
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			if (cur[0] == tx && cur[1] == ty) {
				return true;
			}
			int[] next1 = new int[] { cur[0] + cur[1], cur[1] };
			int[] next2 = new int[] { cur[0], cur[0] + cur[1] };
			if (!(next1[0] > tx || next1[1] > ty) && visited.add(next1[0] + "," + next1[1])) {
				queue.add(next1);
			}
			if (!(next2[0] > tx || next2[1] > ty) && visited.add(next2[0] + "," + next2[1])) {
				queue.add(next2);
			}
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
